Теория автоматов

Теория автоматов [automa­ta theory] — раздел теоретической кибернетики, который изучает математические модели (называемые здесь автоматами или машинами) реальных или возможных устройств, перерабатывающих дискретную ин­формацию дискретными же тактами. Основными понятиями этой теории являются абстрактный автомат и композиция автоматов. Абстрактный автомат — модель, представляющая устройство, которое преобразует информацию в виде «черного ящика», имеющего входы и выходы и некоторое множество внутренних состояний. Когда на входы подается сигнал, то в зависимости от него и текущего состояния автомат переходит в следующее состояние и выдает сигналы на свои выходы. Это — один такт действия автомата. Затем подается следующий сигнал, наступает следующий такт и т.д. Изменение сигналов на входе меняет состояния автомата и его выходные сигналы, т.е. происходят элементарные преобразования поступающей в виде сигналов информации. Композиция автоматов показывает, каким образом из элементарных устройств может быть построено другое, более сложное.

Т.а. позволяет не только конструировать разнообразные вычислительные машины (для чего, собственно, и была создана), но и изучать проблемы математической логики, разработки алгоритмов, программирования для компьютеров.